﻿
namespace Leetcode.N0084;
public class Solution
{
    public int LargestRectangleArea(int[] heights)
    {
        if (heights.Length == 0)
        {
            return 0;
        }

        var s = new System.Collections.Generic.Stack<(int index, int height)>();
        var max = 0;

        for (int i = 0; i < heights.Length; i++)
        {
            while (s.Count > 0 && heights[i] < s.Peek().height)
            {
                var item = s.Pop();
                var width = i - item.index;
                for (int j = item.index - 1; j >= 0; j--)
                {
                    if (heights[j] >= heights[item.index])
                    {
                        width++;
                    }
                    else
                    {
                        break;
                    }
                }
                max = Math.Max(max, width * item.height);
            }

            if (s.Count == 0 || heights[i] > s.Peek().height)
            {
                s.Push((i, heights[i]));
            }
        }

        while (s.Count > 0)
        {
            var item = s.Pop();
            var width = heights.Length - item.index;
            for (int j = item.index - 1; j >= 0; j--)
            {
                if (heights[j] >= heights[item.index])
                {
                    width++;
                }
                else
                {
                    break;
                }
            }

            max = Math.Max(max, width * item.height);
        }


        return max;
    }
}
